Arranging coins [Binary Search]

Time: O(LogN); Space: O(1); easy

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

Input: 5

Output: 2

Explanation:

  • The coins can form the following rows:

    • ¤

    • ¤ ¤

    • ¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

Input: 8

Output: 3

Explanation:

  • The coins can form the following rows:

    • ¤

    • ¤ ¤

    • ¤ ¤ ¤

    • ¤ ¤

Because the 4th row is incomplete, we return 3.

[1]:

import math

class Solution1(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int((math.sqrt(8*n+1)-1) / 2)  # sqrt is O(logn) time.

[2]:

s = Solution1()
n = 5
assert s.arrangeCoins(n) == 2
n = 8
assert s.arrangeCoins(n) == 3

[3]:

class Solution2(object):
    '''
    Time: O(logN); Space: O(1)
    '''
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            if 2 * n < mid * (mid+1):
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

[4]:

s = Solution2()
n = 5
assert s.arrangeCoins(n) == 2
n = 8
assert s.arrangeCoins(n) == 3